10280. Путешествие

 

Казак Ус собирается в путешествие. В Потоколяндии имеются n городов, расположенных на прямой и пронумерованных целыми числами от 1 до n. Каждый город характеризуется определенным значением xi​ – координатой города. Расстояние между городами с номерами i и j равно ∣xj – xi​∣.

 

Казак Ус хочет узнать минимальное расстояние, которое ему предстоит пройти, путешествуя по Потоколяндии, при условии, что он должен побывать в каждом городе хотя бы один раз и завершить путешествие в городе, из которого его начал. Ваша задача – найти минимальную длину маршрута при условии, что город, с которого начнет путешествие Козак, и его маршрут остаются на Ваше усмотрение.

 

Вход. Первая строка содержит одно целое число n (1 ≤ n ≤ 100).

Вторая строка содержит n целых чисел x1​, x2​, …, xn​ (1 ≤ xi​ ≤1000).

 

Выход. Выведите одно целое число – наименьшую длину маршрута Казака Уса.

 

Пример входа 1

Пример выхода 1

2

1 4

6

 

 

 

Пример входа 2

Пример выхода 2

3

1 3 1

4

 

 

 

РЕШЕНИЕ

циклы

 

Анализ алгоритма

Отсортируем координаты городов. Пусть x1​ ≤ x2​ ≤ … ≤ xn. Казак Ус посетит все города с минимальной длиной маршрута, если начнет свой путь в x1, дойдет до xn, а потом вернется обратно в x1. Таким образом он завершит путешествие в городе, из которого его начал.

Длина маршрута составит 2 * (mx – mn), где mx = xn (максимальная абсцисса), mn = x1 (минимальная абсцисса). Для решения задачи достаточно найти наименьшее и наибольшее значение среди xi.

 

Реализация алгоритма

Читаем входное значение n.

 

scanf("%d", &n);

 

Ищем наименьшее mn и наибольшее mx значение среди всех xi.

 

mn = 1000; mx = 0;

for (i = 0; i < n; i++)

{

  scanf("%d", &x);

  if (x > mx) mx = x;

  if (x < mn) mn = x;

}

 

Выводим ответ.

 

printf("%d\n", 2 * (mx - mn));